#include <bits/stdc++.h>
using namespace std;
int a, b;
pair<int, int> exgcd(int a, int b)
{
    //exgcd是gcd的加强版
    //我们想要求x,y使得其满足
    //ax+by=gcd(a,b)
    //由于gcd(a,b)=gcd(b,a%b)
    //原式事实上等于
    //ax+by=gcd(b,a%b)
    //我们现在有x',y'使得
    //bx'+(a mod b)y'=gcd(b,a%b)
    //则
    //ax+by=bx'+(a mod b)y'
    //ax+by=bx'+(a-(a/b)b)y'
    //ax+by=bx'+ay'-(a/b)by'
    //ax+by=ay'+b(x'-(a/b)y')
    //由于两侧对称,可得
    //x=y'
    //y=x'-(a/b)y'
    //如此一来即可递归
    //到b=0即可停止
    //此时x=1,y=0即可满足ax+by=gcd(a,b)
    if (b == 0)
        return make_pair<int, int>(1, 0);
    pair<int, int> tmp = exgcd(b, a % b);
    pair<int, int> ans = make_pair(tmp.second, tmp.first - a / b * tmp.second);
    return ans;
}
int main()
{
    //逆元要满足以下式子
    //ax=1(mod b)
    //x即为a的逆元
    //我们知道,求模实质上是除法
    //如
    //18%5=18-5*3=3
    //那么
    //ax=1(mod p)
    //事实上就是
    //ax-by=1
    //把y写成+的形式就是
    //ax+by=1
    //即得
    //x是a在模b意义下的逆元
    //y是b在模a意义下的逆元
    //即可用exgcd求
    cin >> a >> b;
    auto pr = exgcd(a, b);
    cout << (pr.first % b + b) % b << endl;
    return 0;
}
